package com.zh.note.huawei.twohundred.跳房子2;

import java.util.*;

/**
 * https://dream.blog.csdn.net/article/details/131283858
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // int n = sc.nextInt();
        // String input = sc.nextLine();
        int n = 12;
        String input = "[-1,9,2,4,-1]";
        String[] split = input.replaceAll("[\\[\\]]", "").split(",");
        int[] nums = new int[split.length];
        for (int i = 0; i < split.length; i++) {
            nums[i] = Integer.parseInt(split[i]);
        }
        Deque<Integer> path = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();

        dfs(nums, 0, 0, path, n, res);
        System.out.println(res);
        System.out.println(res.get(0));

    }

    private static void dfs(int[] nums, int startIndex, int sum, Deque<Integer> path, int target, List<List<Integer>> res) {

        if (path.size() == 3) {
            if (sum == target) {
                res.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            sum += nums[i];
            path.addLast(nums[i]);
            dfs(nums, i + 1, sum, path, target, res);
            path.removeLast();
            sum -= nums[i];
        }

    }
}
